package heap.medium;

import java.util.HashMap;
import java.util.PriorityQueue;

/**
 * 重构字符串
 * 示例 1:
 *
 * 输入: S = "aab"
 * 输出: "aba"
 * 示例 2:
 *
 * 输入: S = "aaab"
 * 输出: ""
 */
public class ReorganizeString_767 {

    public String reorganizeString(String s) {
        int[] al = new int[26];
        int maxIndex = 0;
        char maxC = s.charAt(0);
        int threshold = (s.length() + 1) >> 1;
        for (char c : s.toCharArray()) {
            al[c - 'a'] += 1;
            if (al[c - 'a'] > al[maxIndex]) {
                maxC = c;
                maxIndex = c - 'a';
            }
            if (al[maxIndex] > threshold)
                return "";
        }

        char[] res = new char[s.length()];
        int index = 0;
        while(al[maxIndex]-- > 0) {
            res[index] = maxC;
            index += 2;
        }
        int n = 0;
        while(n < al.length) {
            while(al[n]-- > 0) {
                if (index >= res.length)
                    index = 1;
                res[index] = (char)('a' + n);
                index += 2;
            }
            n++;
        }
        return new String(res);
    }

    public String reorganizeStringHeap(String s) {
        HashMap<Character, Integer> map = new HashMap<>();
        for (char c : s.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }

        PriorityQueue<Character> heap = new PriorityQueue<>((a, b) -> map.get(b) - map.get(a));
        for (int i = 0; i < 26; i++) {
            // 'a' + i =>
            if (map.get((char)('a' + i)) == null)
                continue;
            if (map.get((char)('a' + i)) != null)
                heap.offer((char)('a' + i));
            if (map.get((char)('a' + i)) > (s.length() + 1 >> 1))
                return "";
        }
        StringBuilder sb = new StringBuilder();
        while(heap.size() > 1) {
            Character max = heap.poll();
            Character c = heap.poll();
            sb.append(max);
            sb.append(c);

            map.put(max, map.get(max) - 1);
            map.put(c, map.get(c) - 1);
            if (map.get(max) > 0)
                heap.offer(max);
            if (map.get(c) > 0)
                heap.offer(c);
        }

        if (heap.size() > 0) {
            sb.append(heap.poll());
        }
        return sb.toString();
    }


    public static void main(String[] args) {
        ReorganizeString_767 rs = new ReorganizeString_767();
        rs.reorganizeStringHeap("vvvlo");
    }
}
